package Queue_and_Stack;

import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;

/*
字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像3a或2[4]的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/queue-stack/gdwjv/
 */

public class _53字符串解码 {
    public static void main(String[] args) {
        String s = "3[a2[c]]";

        String s1 = decodeString(s);
        System.out.println(s1);

    }

    //栈操作
    public static String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        Deque<Character> chars = new ArrayDeque<>();
        Deque<Integer> nums = new ArrayDeque<>();
        int num = 0;

        for (int i = 0; i < s.length(); i++) {

            while (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                num = num * 10 + s.charAt(i) - '0';
                i++;
                if(!(s.charAt(i) >= '0' && s.charAt(i) <= '9')){
                    nums.push(num);
                    num = 0;
                }
            }
            if (s.charAt(i) == '[') {
                chars.push(s.charAt(i));
                continue;
            }

            if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z'){
                chars.push(s.charAt(i));
                continue;
            }
            if(s.charAt(i) == ']'){
                StringBuilder temp = new StringBuilder();
                Character poll = chars.poll();
                while (!chars.isEmpty() && poll != '['){
                    temp.append(poll);
                    poll = chars.poll();
                }
                temp.reverse();
                int pop = nums.pop();
                if(chars.isEmpty()){
                    for (int j = 0; j < pop; j++) {
                        sb.append(temp);
                    }
                }else {
                    for (int j = 0; j < pop; j++) {
                        for (int i1 = 0; i1 < temp.length(); i1++) {
                            chars.push(temp.charAt(i1));
                        }
                    }
                }
            }
        }
        while(!chars.isEmpty()){
            Character pop = chars.pollLast();
            sb.append(pop);
        }
        return sb.toString();
    }

    //官解：栈操作
    //if (Character.isDigit(cur)) 获取一个数字并进栈  cur是数字
    //else if (Character.isLetter(cur) || cur == '[')    cur是字母 或 [
    class Solution {
        int ptr;

        public String decodeString(String s) {
            LinkedList<String> stk = new LinkedList<String>();
            ptr = 0;

            while (ptr < s.length()) {
                char cur = s.charAt(ptr);
                if (Character.isDigit(cur)) {
                    // 获取一个数字并进栈
                    String digits = getDigits(s);
                    stk.addLast(digits);
                } else if (Character.isLetter(cur) || cur == '[') {
                    // 获取一个字母并进栈
                    stk.addLast(String.valueOf(s.charAt(ptr++)));
                } else {
                    ++ptr;
                    LinkedList<String> sub = new LinkedList<String>();
                    while (!"[".equals(stk.peekLast())) {
                        sub.addLast(stk.removeLast());
                    }
                    Collections.reverse(sub);
                    // 左括号出栈
                    stk.removeLast();
                    // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                    int repTime = Integer.parseInt(stk.removeLast());
                    StringBuffer t = new StringBuffer();
                    String o = getString(sub);
                    // 构造字符串
                    while (repTime-- > 0) {
                        t.append(o);
                    }
                    // 将构造好的字符串入栈
                    stk.addLast(t.toString());
                }
            }

            return getString(stk);
        }

        public String getDigits(String s) {
            StringBuffer ret = new StringBuffer();
            while (Character.isDigit(s.charAt(ptr))) {
                ret.append(s.charAt(ptr++));
            }
            return ret.toString();
        }

        public String getString(LinkedList<String> v) {
            StringBuffer ret = new StringBuffer();
            for (String s : v) {
                ret.append(s);
            }
            return ret.toString();
        }
    }

}
